package com.example.algorithm.huawei_rongyao_29;

import java.util.Scanner;
import java.util.Stack;

// 括号字符串的有效性
// 难度：简单
// 关联题：Q01_LongestValidParentheses

/**
 * 要判断给定的字符串是否是整体有效的括号字符串，可以使用栈来实现括号匹配。
 * 遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶元素是否是与之匹配的左括号，如果是则出栈，继续遍历，如果不是则返回"NO"，如果遍历结束后栈为空，则返回"YES"，否则返回"NO"。
 * 这个和之前那个Q问题的区别是，那个是找最长的有效括号字符串子串。这个是直接给定一个，判断它是否整体有效。有相似之处也有区别。
 * <p>
 * (())   YES
 * ()()   YES
 * (()()) YES
 * ()a()  NO 
 * ()(()  No
 * ())()  No
 * ()())  No
 */
public class Q10_ValidParentheses {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String result = isValidParentheses(str) ? "YES" : "NO";
        System.out.println(result);
        scanner.close();
    }

    public static boolean isValidParentheses(String str) {
        Stack<Character> stack = new Stack<>();
        // 用int i = 0; i < s.length(); i++搭配chatAt()也可以
        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                // 入栈
                stack.push(ch);
            } else if (ch == ')') {

                //右边括号进来。满足栈为空的情况的只有：
                // 1、首个括号就位右括号。我个人把这种情形称之为：首位右括。
                // 2、虽然不是首个括号为右括号，但是前面的括号是左右正常配对的。我把这种情形称之为：抵消后的首位右扩
                // 一旦出现首位右括或者抵消后的首位右括，那么，意味着没有再继续遍历下去的理由了。后面无论出现什么，都无法与这个首位右扩匹配
                // 那么，这意味着整个字符串，都是false的。所以，下面就直接返回false，结束了整个判定过程。
                if (stack.isEmpty()) {
                    return false;
                }

                // 如果右扩进来，不是首位右扩的情况。那么，其实是说明，栈中存在可以抵消的左括。我把这种称之为，栈中左括存量。
                // 那就匹配消耗一个栈中左括存量。
                char top = stack.pop();
            } else {
                // 字符串中包含非括号字符。直接判定整个字符串不符合规则
                return false;
            }
        }

        return stack.isEmpty(); // 如果栈为空，则括号匹配成功，返回true；否则返回false
    }
}

